Partition of a Binary Matrix into k (k ≥ 3) Exclusive Row and Column Submatrices Is Difficult
Joint Authors
Xiao, Jinjie
Liu, Peiqiang
Mao, Yanyan
Zhu, Daming
Xie, Qingsong
Source
Mathematical Problems in Engineering
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-13, 13 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-07-03
Country of Publication
Egypt
No. of Pages
13
Main Subjects
Abstract EN
A biclustering problem consists of objects and an attribute vector for each object.
Biclustering aims at finding a bicluster—a subset of objects that exhibit similar behavior across a subset of attributes, or vice versa.
Biclustering in matrices with binary entries (“0”/“1”) can be simplified into the problem of finding submatrices with entries of “1.” In this paper, we consider a variant of the biclustering problem: the k-submatrix partition of binary matrices problem.
The input of the problem contains an n×m matrix with entries (“0”/“1”) and a constant positive integer k.
The k-submatrix partition of binary matrices problem is to find exactly k submatrices with entries of “1” such that these k submatrices are pairwise row and column exclusive and each row (column) in the matrix occurs in exactly one of the k submatrices.
We discuss the complexity of the k-submatrix partition of binary matrices problem and show that the problem is NP-hard for any k≥3 by reduction from a biclustering problem in bipartite graphs.
American Psychological Association (APA)
Liu, Peiqiang& Zhu, Daming& Xiao, Jinjie& Xie, Qingsong& Mao, Yanyan. 2014. Partition of a Binary Matrix into k (k ≥ 3) Exclusive Row and Column Submatrices Is Difficult. Mathematical Problems in Engineering،Vol. 2014, no. 2014, pp.1-13.
https://search.emarefa.net/detail/BIM-509392
Modern Language Association (MLA)
Liu, Peiqiang…[et al.]. Partition of a Binary Matrix into k (k ≥ 3) Exclusive Row and Column Submatrices Is Difficult. Mathematical Problems in Engineering No. 2014 (2014), pp.1-13.
https://search.emarefa.net/detail/BIM-509392
American Medical Association (AMA)
Liu, Peiqiang& Zhu, Daming& Xiao, Jinjie& Xie, Qingsong& Mao, Yanyan. Partition of a Binary Matrix into k (k ≥ 3) Exclusive Row and Column Submatrices Is Difficult. Mathematical Problems in Engineering. 2014. Vol. 2014, no. 2014, pp.1-13.
https://search.emarefa.net/detail/BIM-509392
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-509392